package problem132;

//132.分割回文串2
//https://leetcode.cn/problems/palindrome-partitioning-ii/

class Solution {
    public int minCut(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n];
        for(int i = n-1; i>=0; i--) {
            for(int j = i; j<n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i == j || i+1 == j) isPal[i][j] = true;
                    else isPal[i][j] = isPal[i+1][j-1];
                }
            }
        }
        int[] dp = new int[n];
        for(int i = 1; i<n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for(int i = 0; i<n; i++) {
            for(int j = 1; j<=i; j++) {
                if(isPal[0][i]) dp[i] = 0;
                else if(isPal[j][i])  dp[i] = Math.min(dp[i], dp[j-1]+1);
            }
        }
        return dp[n-1];
    }
}

/*

isPal[i][j]:从i到j的字符串能否构成回文
dp[i]:从0到第i个字符串分割成回文的最少分割次数

*/